package tree;

/**
 * @author kaho
 * @since 2021/2/22
 */
public class _98_验证二叉搜索树 {

    /**
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     * <p>
     * 假设一个二叉搜索树具有如下特征：
     * <p>
     * 节点的左子树只包含小于当前节点的数。
     * 节点的右子树只包含大于当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * <p>
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param root
     * @return
     */
    public static long pre = Long.MIN_VALUE;

    public static boolean isValidBST1(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val<pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }



    public static boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val<=pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(0);
//        TreeNode root2 = new TreeNode(4);
//        TreeNode root3 = new TreeNode(6);
//        TreeNode root4 = new TreeNode(3);
//        TreeNode root5 = new TreeNode(7);
//        root1.left = root2;
//        root1.right = root3;
//        root3.left = root4;
//        root3.right = root5;
        boolean validBST = isValidBST(root1);
    }
}
